import { MatrixEdge } from "./MatrixEdge";

export class MatrixGraph {
    
    private _edges:Array<MatrixEdge>;
    private _points:Array<Array<number>>;
    constructor(){
        this._edges = [];
    }

    public addEdge(p1Num:number,p2Num:number,edgeWeight:number){
        let newEdge:MatrixEdge = new MatrixEdge(p1Num,p2Num,edgeWeight);
        this._edges.push(newEdge);
    }

    public setAllPoint(allPoints:Array<Array<number>>):Array<Array<number>>{
        this._points = [];
        for(let p of allPoints){
            this._points.push([Math.round(p[0]),Math.round(p[1])]);
        }
        return this._points;
    }
    public getAllPoints(){return this._points;}

    /**
     * 用Prim加点法求最小生成树
     */
    public getMinimumSpanningTree():Array<MatrixEdge>{
        let tree:Array<MatrixEdge> = [];
        let open:Array<number> = [];
        let waitting:Array<number> = this._getPs();
        let waittingEdges:Array<MatrixEdge> = [].concat(this._edges);
        
        let moveToOpen = function(p:number){
            if(!open.includes(p)) open.push(p);
            for(let i=0;i<waitting.length;i++){
                if(waitting[i] === p){
                    waitting.splice(i,1);
                    break;
                }
            }
        }

        let getNextP = function(){
            let nearestEdge:MatrixEdge = getNearestEdge();
            waittingEdges.splice(waittingEdges.indexOf(nearestEdge),1);
            
            return nearestEdge;
        }

        //得到离整个树最近的边
        let getNearestEdge = function(){
            let nearest:MatrixEdge;
            for(let openPoint of open){
                for(let edge of waittingEdges){
                    if(edge.getP1Num() === openPoint || edge.getP2Num() === openPoint){
                        //保证该连线的两个端点不在一个树中
                        if(edge.getP1Num() === openPoint && open.includes(edge.getP2Num())){
                            continue;
                        }

                        if(edge.getP2Num() === openPoint && open.includes(edge.getP1Num())){
                            continue;
                        }
                        
                        if(!nearest){
                            nearest = edge;
                            continue;
                        }

                        if(nearest.getWeight() > edge.getWeight()){
                            nearest = edge;
                            continue;
                        }
                    }
                }
            }
            
            return nearest;
        }

        let recursion = function(){
            if(waitting.length > 0){
                let edge:MatrixEdge = getNextP();
                if(!edge) return;
                
                moveToOpen(edge.getP1Num());
                moveToOpen(edge.getP2Num());
                tree.push(edge)
                if(waitting.length){
                    recursion();
                }
            }
        }
        
        
        moveToOpen(waitting[0]);
        recursion();
        return tree;
    }

    public getLinePair(pointIdxArray:Array<number>):Array<Array<number>>{
        let pairs:Array<Array<number>> = [];
        for(let i=0;i<pointIdxArray.length;i++){
            if(i !== 0){
                pairs.push([pointIdxArray[i-1],pointIdxArray[i]]);
            }
        }
        return pairs;
    }
    
    public getLines(edge:Array<MatrixEdge>):Array<Array<number>>{
        let pairs:Array<Array<number>> = [];
        for(let i=0;i<edge.length;i++){
            pairs.push([edge[i].getP1Num(),edge[i].getP2Num()]);
        }
        return pairs;
    }

    private _getPs(){
        let ps = [];
        let addP = function(p){
            if(ps.includes(p)) return;
            ps.push(p)
        }
        for(let edge of this._edges){
            addP(edge.getP1Num());
            addP(edge.getP2Num());
        }
        return ps;
    }
}